package cn.chen.数据结构.递归;

/**
 * 迷宫问题：在一个宫格中，找到一个点到另一个点的路径
 * 地图周围都是墙，设置为1
 * 地图中间也有墙，设置为1
 * 走过能通的点，设置为2
 * 走过不能通的点，设置为3
 *
 * 设置一个规则：先往下--》往右--》往上--》往左
 *
 * */
public class MazeRecursion {

    public static void main(String[] args){

        // 定义一个图
        int[][] map=new int[8][7];
        // 周围一圈都是墙1
        for(int i=0;i<7;i++){

            map[0][i]=1;
            map[7][i]=1;
        }
        for(int i=1;i<7;i++){

            map[i][0]=1;
            map[i][6]=1;
        }
        map[4][1]=1;
        map[4][2]=1;
        map[4][3]=1;
        map[3][3]=1;
        map[2][3]=1;
        map[2][2]=1;

        // 打印一次图
        for(int i=0;i<8;i++){

            for(int j=0;j<7;j++){

                System.out.print(map[i][j]+"\t");
            }
            System.out.println();
        }

        // 调用方法来找到正确的路
        boolean boo=setWay(map,1,1);    // 当方法的返回值为true时，才说明找到了路，返回为false，表示没有找到路

        System.out.println("找到路之后的图");
        for(int i=0;i<8;i++){

            for(int j=0;j<7;j++){

                System.out.print(map[i][j]+"\t");
            }
            System.out.println();
        }

    }
    // 递归找路的方法

    /**
     * @param map   这就是迷宫的地图，一个二维数组
     * @param i     这就是表示行
     * @param j     这就是表示列
     * @return      返回true表示这个点可以通
     */
    public static boolean setWay(int[][] map,int i,int j){

        if(map[6][5]==2){   // 这就是我们要找的点，当这个点为2，表示已经找到这个路径了

            return true;
        }
        else {
            if(map[i][j]==0) { // 表示该点没有走过，也不是墙
                map[i][j]=2;    // 假定这个点可以通，所以先设置为2，但是要看该点上下左右能不能走通，如果能，这个点才是真的通了
                if(setWay(map,i+1,j)) // 向下走
                    return true;    // 这就是表示i,j这个点可以走通
                else if(setWay(map,i,j+1))  // 向右走
                    return true;
                else if(setWay(map,i-1,j))  // 向上走
                    return true;
                else if(setWay(map,i,j-1))  // 向左走
                    return true;
                else {// 这就是上下左右都走不通，所以就返回false
                    map[i][j]=3;    // 该点，上下左右都走不通，所以将该点设置为3
                    return false;
                }
            }
            else    // 这里表示该点可能你表示的是 1 2 3 ，所以该点都不需要再探测了，所以直接返回false
                return false;
        }
    }
}
